package org.example.Soution002;

import java.util.*;

public class courseFinish {
    public static void main(String[] args) {
        int[][] courses={{1,0}};
        courseFinish obj=new courseFinish();
        System.out.println(obj.canFinish(2,courses));
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //创建一个list保存每门课的后置课程
        List<List<Integer>> courseList = new ArrayList<>();
        for(int i=0;i<numCourses;i++){
            courseList.add(new ArrayList<>());

        }

        //记录每门课的入度（前置节点）
        int[] preCourse=new int[numCourses];
        for(int i=0;i<prerequisites.length;i++){
            int course=prerequisites[i][0];
            int pre=prerequisites[i][1];
            preCourse[course]++;
            courseList.get(pre).add(course);
        }

        //记录无前置条件的课程为初始循环点
        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i< preCourse.length;i++){
            if(preCourse[i]==0){
                queue.add(i);
            }
        }

        //能完成的课程
        int count=0;
        while(!queue.isEmpty()){
            int course=queue.poll();
            count++;
            List<Integer> temp=courseList.get(course);
            for(int i=0;i<temp.size();i++){
                if(--preCourse[temp.get(i)]==0){
                    queue.add(temp.get(i));
                }
            }
        }
        return count==numCourses;
    }
}
